//某二叉树的先序遍历结果记录于整数数组 preorder，它的中序遍历结果记录于整数数组 inorder。请根据 preorder 和 inorder 的提示
//构造出这棵二叉树并返回其根节点。 
//
// 
//
// 注意：preorder 和 inorder 中均不含重复数字。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
//
//输出: [3,9,20,null,null,15,7]
// 
//
// 
//
// 示例 2: 
//
// 
//输入: preorder = [-1], inorder = [-1]
//
//输出: [-1]
// 
//
// 
//
// 提示: 
//
// 
// 1 <= preorder.length <= 3000 
// inorder.length == preorder.length 
// -3000 <= preorder[i], inorder[i] <= 3000 
// inorder 均出现在 preorder 
// preorder 保证 为二叉树的前序遍历序列 
// inorder 保证 为二叉树的中序遍历序列 
// 
//
// 
//
// 注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-
//preorder-and-inorder-traversal/ 
//
// 
//
// Related Topics 树 数组 哈希表 分治 二叉树 👍 1148 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author ldltd
 * @date 2025-04-22 23:53:36
 * @description LCR 124.推理二叉树
 */
public class ZhongJianErChaShuLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ZhongJianErChaShuLcof fun=new ZhongJianErChaShuLcof();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

 // Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
 
class Solution {
    /*
递归，时间On 空间on
	对于任意一颗树而言，前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
	即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
*/


    private Map<Integer,Integer> map;
    public TreeNode deduceTree1(int[] preorder, int[] inorder) {
        int n=preorder.length;
        //构造hash,通过节点值定位index
        map=new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++) {
            map.put(inorder[i],i);
        }
        return my(preorder,inorder,0,n-1,0,n-1);
    }
    private TreeNode my(int[] pre, int[] in, int pre_l, int pre_r, int in_l, int in_r){
        if(pre_l>pre_r){
            return null;
        }
        //先序遍历的第一个节点就是根节点
        int pre_root=pre_l;
        //从终须遍历中定位根节点（题目中，无重复元素）
        int in_root=map.get(pre[pre_root]);
        //建立根节点
        TreeNode root = new TreeNode(pre[pre_root]);
        //计算左子树节点
        int l_size=in_root-in_l;
        //构造左右子树，并连接到根节点，其中先序从左边界+1的l_size对应中序左边界到根节点-1的元素
        root.left=my(pre,in,pre_l+1,pre_l+l_size,in_l,in_root-1);
        //先序左边界+l_size+1到pre_r对应中序根节点+1到右边界
        root.right=my(pre,in,pre_l+l_size+1,pre_r,in_root+1,in_r);
        return root;
    }
    /*
    *我们用一个栈保存已经遍历过的节点，遍历前序遍历的数组，一直作为当前根节点的左子树，
    * 直到当前节点和中序遍历的数组的节点相等了，那么我们正序遍历中序遍历的数组，
    * 倒着遍历已经遍历过的根节点（用栈的 pop 实现），找到最后一次相等的位置，把它作为该节点的右子树。
    上边的分析就是迭代总体的思想，代码的话还有一些细节注意一下。
    * 用一个栈保存已经遍历的节点，用 curRoot 保存当前正在遍历的节点。
*/
    public TreeNode deduceTree2(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        Stack<TreeNode> roots = new Stack<TreeNode>();
        int pre = 0;
        int in = 0;
        //先序遍历第一个值作为根节点
        TreeNode curRoot = new TreeNode(preorder[pre]);
        TreeNode root = curRoot;
        roots.push(curRoot);
        pre++;
        //遍历前序遍历的数组
        while (pre < preorder.length) {
            //出现了当前节点的值和中序遍历数组的值相等，寻找是谁的右子树
            if (curRoot.val == inorder[in]) {
                //每次进行出栈，实现倒着遍历
                while (!roots.isEmpty() && roots.peek().val == inorder[in]) {
                    curRoot = roots.peek();
                    roots.pop();
                    in++;
                }
                //设为当前的右孩子
                curRoot.right = new TreeNode(preorder[pre]);
                //更新 curRoot
                curRoot = curRoot.right;
                roots.push(curRoot);
                pre++;
            } else {
                //否则的话就一直作为左子树
                curRoot.left = new TreeNode(preorder[pre]);
                curRoot = curRoot.left;
                roots.push(curRoot);
                pre++;
            }
        }
        return root;

    }
    //迭代算法在大多数情况下可以正确重建二叉树，但某些情况可能会失败
    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);
        int in = 0;
        for (int pre = 1; pre < preorder.length; pre++) {
            TreeNode curr = new TreeNode(preorder[pre]);
            TreeNode parent = null;
            while (!stack.isEmpty() && stack.peek().val == inorder[in]) {
                parent = stack.pop();
                in++;
            }
            if (parent != null) {
                parent.right = curr;
            } else {
                stack.peek().left = curr;
            }
            stack.push(curr);
        }
        return root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
